package leetcode.problems;

/**
 * _0412 House Robber
 * 房子强盗
 * Created by gmwang on 2018/3/23
 */
public class _0413HouseRobber {
    /**
     *  You are a professional robber planning to rob houses along a street.
     *  Each house has a certain amount of money stashed,
     *  the only constraint stopping you from robbing each of them is that adjacent
     *  houses have security system connected and it will automatically contact the police
     *  if two adjacent houses were broken into on the same night.

     Given a list of non-negative integers representing the amount of money of each house,
     determine the maximum amount of money you can rob tonight without alerting the police.
     *
     *
     *   你是一名专业的强盗，计划抢劫沿街的房屋。每间房屋都藏有一定数量的金钱，
     *   唯一阻止你抢劫每间房屋的限制因素是邻近的房屋有保安系统连接，
     *   如果在同一晚上有两间相邻的房屋被闯入，它将自动与警方联系。
     给出一份代表每个房屋的金额的非负整数列表，确定你可以在没有提醒警方的情况下抢劫的最高金额。
     */
    /**
     * 思路：
     * 1. 以{6, 6, 8, 10}为例
     * 2. 先记录x1=6，再记录 x2 = 6,
     * 3. 比较 x1= (6+8 和x2 的较大值)
     * 4. 此时 x1=14,x2=6
     * 5. 最后 x2= ((6+10 和x1 的较大值))
     *
     * @param
     * @return
     */
    public static int rob(int[] nums) {
//        int a = 0, b = 0, temp;
//        for (int i : nums) {
//            temp = b;
//            b = Math.max(b, a + i);
//            a = temp;
//        }
//        return b;
        int prevNo = 0;
        int prevYes = 0;
        for (int n : nums) {
            int temp = prevNo;
            prevNo = Math.max(prevNo, prevYes);
            prevYes = n + temp;
        }
        return Math.max(prevNo, prevYes);
    }

    public static void main(String[] args) {
        int[] nums = {6, 6, 8, 10};
        System.out.println(rob(nums));
//        System.out.println(Test.s);
//        Test.s = 2;
//        System.out.println(Test.s);
    }
}
